package tianhao.luo.linkedlist;

import lombok.Data;

import java.util.Stack;

/**
 * 模拟单链表
 *
 * @author: tianhao.luo@hand-china.com 2021/6/14  9:39
 */
@Data
public class SingleLinkedList {

    /**
     * 必须有的头节点
     * 不存放具体数据,只是用来标记链表的开头
     */
    private HeroNode head = new HeroNode(0, "", "");

    /**
     * 给链表添加元素
     * 1.确定链表的尾部节点
     * 2.将尾部节点的next指向当前添加的元素
     *
     * @param heroNode 新加节点
     */
    public void add(HeroNode heroNode) {
        // 通过操作临时变量的next指针,来寻找尾部节点
        HeroNode temp = head;

        while (true) {
            // temp节点的next不为空,表示还不是尾部数据
            if (temp.next != null) {
                temp = temp.next;
                continue;
            }
            // 是尾部数据了,更新节点的尾部信息
            temp.next = heroNode;
            break;
        }
    }

    /**
     * 展示链表中所有数据
     */
    public void list() {
        // 判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        // 通过操作临时变量的next指针,来寻找尾部节点
        // 输出信息不要包含头节点
        HeroNode temp = head.next;

        while (true) {
            System.out.println("当前节点信息:" + temp.toString());
            // temp节点的next不为空,表示还不是尾部数据
            if (temp.next != null) {
                temp = temp.next;
            } else {
                break;
            }
        }
    }

    /**
     * 进行插入时,需要按照heroNode节点的no顺序插入
     * 1.从前往后,找出no恰好刚小于heroNode的no的节点less
     * 2.将heroNode的next更新为less的next,将less的next更新为heroNode
     * <p>
     * 特殊情况:
     * 1.链表恰好为空,此时heroNode就是尾部节点
     *
     * @param heroNode 插入的节点
     */
    public void addByOrder(HeroNode heroNode) {
        // 找出less节点
        HeroNode less = head;

        while (true) {
            if (less.next == null){
                less.next = heroNode;
                break;
            }
            // 从前往后移动,如果插入节点小于less的next节点的no,则插入这个位置
            if (heroNode.getNo() < less.next.getNo()) {
                // 插入操作: 将heroNode放入less和less.next之间
                // 1. 插入节点的next指向less的next
                // 2. less的next指向插入节点
                heroNode.next = less.next;
                less.next = heroNode;
                break;
            } else if (heroNode.getNo() == less.next.getNo()) {
                throw new RuntimeException("插入了相同no的数据");
            }
            // 如果插入节点的no大于less的next节点的no,则less需要后移
            less = less.next;
        }
    }


    /**
     * 更新同no的节点信息
     *
     * 找出同no的节点数据,从前往后遍历
     * @param heroNode 更新的节点
     */
    public void update(HeroNode heroNode){

        HeroNode temp = head.next;
        if (temp == null){
            System.out.println("链表为空,无法查找");
            return;
        }
        while (true){
            // 找到结尾都没有
            if (temp == null){
                System.out.println("数据不存在~");
                break;
            }

            if (temp.no == heroNode.no) {
                // 更新
                temp.setName(heroNode.getName());
                temp.setNickName(heroNode.getNickName());
                break;
            }
            // 未找见,后移
            temp = temp.next;
        }
    }



    /**
     * 删除同no的节点
     *
     * 找出同no的节点数据,从前往后遍历
     * 1. 链表中将被删除节点A,将A的前一位的next指向A的next
     *
     * @param heroNode 删除
     */
    public void delete(HeroNode heroNode){

        HeroNode temp = head;
        if (temp.next == null){
            System.out.println("链表为空,无法删除");
            return;
        }

        while (true){
            // 找到结尾都没有
            if (temp.next == null){
                System.out.println("数据不存在~");
                break;
            }
            // 找到删除节点的前一个节点
            if (temp.next.no == heroNode.no) {
                // temp就是heroNode的前一位
                // 删除
                temp.next = temp.next.next;
                break;
            }
            // 未找见,后移
            temp = temp.next;
        }
    }


    /**
     * 获取链表长度,从头开始,直到最后一个节点
     * @param head 头节点
     * @return 除头节点外的长度
     */
    public static int getLength(HeroNode head){

        HeroNode temp = head;

        if (temp.next == null){
            System.out.println("链表为空..");
            return 0;
        }

        int length = 0;
        while (true){
            if (temp.next != null){
                length++;
            }else {
                break;
            }
            temp = temp.next;
        }
        return length;
    }


    /**
     * 获取倒数第k个节点
     *
     * 1.获取到有效长度
     * 2.将有效长度-k,就是需要的那个元素
     * @param head
     * @param k
     * @return
     */
    public static HeroNode getLastIndexNode(HeroNode head, int k){
        // 如果链表为空,返回null
        if (head.next == null){
            System.out.println("链表为空");
            return null;
        }

        int length = getLength(head);
        if (k <=0 || k >length){
            System.out.println("获取的范围不正确");
            return null;
        }
        int index = length - k;
        // 第二种返回方式
        HeroNode temp = head.next;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;

//        第一种返回方式
//        HeroNode temp = head;
//        int tempInt=0;
//        while (true){
//            temp = temp.next;
//            if (index == tempInt){
//                return temp;
//            }
//            tempInt++;
//        }
    }

    /**
     * 反转链表
     *
     * 1.使用一个临时的头来存放反转后的节点形成一个新链表
     * 2.从旧链表中取出的元素,要放在新链表的第一个元素;且取出的元素的next要指向新链表之前的第一个元素
     * 3.将临时的头的第一个节点,交还给原链表的头节点的next
     */
    public void reverseList(){

        if (head.next == null){
            System.out.println("链表为空");
            return;
        }

        HeroNode reverseHead = new HeroNode(0,"","");
        HeroNode newNode=null;
        HeroNode originalNode = head.next;

        while (originalNode !=null){
            // 将取出来的节点交给新链表,并且每次取出的都要放在开头;同时新链表指向的第一个节点要作为新加入节点的next

            // 将遍历中的原链表中节点的next,临时存放起来
            newNode = originalNode.next;
            // 将新链表中第一个元素交给遍历中元素的next,即在新链表中插入一个元素
            originalNode.next = reverseHead.next;
            // 该元素为新链表中第一个元素
            reverseHead.next = originalNode;
            // 更新遍历的节点
            originalNode = newNode;
        }
        head.next = reverseHead.next;
    }


    /**
     * 逆序打印链表内容
     * @param head 链表的第一个元素
     */
    public static void reversePrint(HeroNode head){
        if (head.next == null){
            return;
        }

        Stack<HeroNode> heroNodeStack = new Stack<>();
        HeroNode temp = head.next;
        // 遍历元素为空,表示走到了末尾
        while (temp != null){
            heroNodeStack.push(temp);
            temp = temp.next;
        }

        int maxSize = heroNodeStack.size();
        for (int i = 0; i < maxSize; i++) {
            HeroNode pop = heroNodeStack.pop();
            System.out.println(pop.toString());
        }
    }


    // todo 合并两个有序的链表
    // 1.新建一个头节点
    // 2.先遍历其中一个链表,加入一个到新的头节点后,然后判断另外一个链表的第一个元素是否需要加入
}
